1. Field of the Invention
The present invention relates to testing of integrated network devices such as network interface devices configured for sending and receiving data packets according to a prescribed protocol such as IEEE 802.3 protocol, and testing of integrated network switches configured for switching the data packets between subnetworks.
2. Background Art
Local area networks use a network cable or other media to link stations on the network. Each local area network architecture uses a media access control (MAC) enabling a network interface card at each station to share access to the media.
The Ethernet protocol ISO/IEC 8802-3 (ANSI/IEEE Std. 802.3, 1993 edition) defines a half-duplex media access mechanism that permits all stations to access the network channel with equality. Each station includes an Ethernet interface card that uses carrier-sense multiple-access with collision detection (CSMA/CD) to listen for traffic on the media. Transmission by a station begins after sensing a deassertion of a receive carrier, indicating no network traffic. After starting transmission, a transmitting station will monitor the media to determine if there has been a collision due to another station sending data at the same time. If a collision is detected, both stations stop, wait a random amount of time, and retry transmission.
Any station can attempt to contend for the channel by waiting a predetermined transmission delay interval after the deassertion of the receive carrier, known as the interpacket gap (IPG) interval. If a plurality of stations have data to send on the network, each of the stations will attempt to transmit in response to the sensed deassertion of the receive carrier on the media and after the IPG interval, resulting in a collision.
Ethernet network nodes mediate collisions using a truncated binary exponential backoff (TBEB) algorithm, which provides a controlled pseudorandom mechanism to enforce a collision backoff interval before retransmission is attempted. According to the truncated binary exponential backoff algorithm, a station keeps track of the number of transmission attempts (j) during the transmission of a current frame. The station computes a collision backoff interval as a randomized integer multiple of a slot time interval, and attempts retransmission after the collision backoff interval. The station will attempt to transmit under the truncated binary exponential algorithm a maximum of sixteen times.
The collision backoff interval is calculated by selecting a random number of slot times from the range of zero to 2j−1. For example, if the number of attempts j=3, then the range of randomly selected number of slot times is [0,7]; if the randomly-selected number of slot times is four, then the collision backoff interval will be equal to four slot time intervals. According to Ethernet protocol, the maximum range of randomly selected slot times is 210−1.
FIG. 1 is a flow diagram illustrating operation of the truncated binary exponential backoff (TBEB) algorithm, where the exponential range of randomly selected integers is based upon an integer value j corresponding to the value of an attempt counter (NA), such that j=(NA). Hence, the operation of FIG. 1 can be characterized by the function f(j)=TBEB(j).
The TBEB algorithm according to the operation TBEB(j) begins in step 10, where the MAC checks if the value j is greater than or equal to ten. If the operand j is less than ten in step 10, then an exponential number of access attempts (A) is determined in step 12 according to the equation A=2j−1. If in step 10 the operand j is greater than or equal to 10, the MAC then checks in step 14 if j equals 16. If j equals 16, then the frame or data packet to be transmitted is discarded in step 16 in accordance with Ethernet (ANSI/IEEE 802.3) protocol. If j is less than 16 in step 14, then the exponential number of access attempts is set in step 18 to A=210−1, or 1023.
After calculating the exponential number of access attempts A, the MAC randomly selects an integer value (k) in step 20 from the range between zero and the exponential number of access attempts and having a maximum value of 1023. The MAC then calculates the delay time (tD) in step 22 by multiplying the predetermined slot time (tS) with the randomly selected integer k.
A slot time (tS) has a duration equal to 512 bit times for 10 and 100 Mbits/s networks. Hence, a slot time will have a duration of 51.2 microseconds in a 10 megabit per second network and 5.12 microseconds in a 100 megabit per second network. The slot time (tS) for a 1000 Mbit/s network is selected in accordance with the network topology and propagation delay, and may have a duration equal to 4096 bit times.
Switched local area networks such as Ethernet (IEEE 802.3) based systems are encountering increasing demands for higher speed connectivity, more flexible switching performance, and the ability to accommodate more complex network architectures. Hence, network switch designers and test engineers need to be able to minimize the time and expense needed to evaluate designs during prototyping of Ethernet-based network systems.
However, operational testing of network devices having a media access controller may be insufficient for adequately testing the randomness of the TBEB algorithm implemented within the media access controller. In particular, conventional testing schemes of connecting a network device under test to a network emulator are incapable of determining whether the MAC within the device under test provides a reliable random selection of slot times, as required under IEEE 802.3; hence, an insufficiently tested network device that is deployed in a network may over time develop a bias for selecting lower numbers of slot times (and unfairly capture the medium), or a bias for selecting high numbers of slot times (resulting in a relative inability to successfully arbitrate with other devices during collision mediation).